A fundamental problem in the field of data storage and communication is the development of practical decoding methods for error-correcting codes (ECC), see Lin et al., “Error Control Coding: Fundamentals and Applications,” Prentice Hall: Englewood Cliffs, N.J., 1983, Peterson et al., “Error-Correcting Codes,” 2nd edition, MIT Press: Cambridge, Mass., 1972, and MacWilliams et al., “The Theory of Error-Correcting Codes,” North-Holland: New York, N.Y., 1977.
An important class of such decoding methods include the prior art iterative decoding methods exemplified by the a posteriori probability propagation (APP) decoding method, and the belief propagation (BP) decoding method, which is also known as the “sum-product” decoding method. A large variety of other related decoded methods are based on simplifications or other alterations of the APP or BP decoding methods. A collection of papers on these decoding methods is contained in the “Special Issue on Codes on Graphs and Iterative Algorithms,” IEEE Transactions on Information Theory, 47(2), February 2001.
These decoding methods use a representation of the code, which is specified by a generalized parity check (GPC) matrix, see Mackay, “Relationships between Sparse Graph Codes,” Proceedings of IBIS 2000. The decoding performance of these methods normally depends on the GPC matrix used to represent the code.
Basic Definitions for Binary Linear Block Error-Correcting Codes
Any references to “codes” herein specifically mean binary linear block error-correcting codes. The basic idea behind these codes is to encode messages of k bits using blocks of N bits, where N>k. The additional N−k bits are used to decode corrupted messages. Corruption can be caused by failure in the storage media or noise in the transmission channel.
A code C is defined by set of 2k possible blocks of code words having a bit length N. A code with parameters N and k is often referred to as an (N, k) code. Codes are normally much more effective when N and k are large. However, as the size of the parameters N and k increase, so does the difficulty of decoding corrupted messages.
Generalized Parity Check GPC Matrices
A binary block code is “linear” if the modulo 2 sum of any two code-words also is a code-word. For example, the modulo 2 sum of 1110100 and 0111010 is 1001110. When a binary block code is linear, the modulo 2 sum of any two code-words form another code-word. Linear codes can be represented by a generalized parity check (GPC) matrix. In fact, a linear code may be represented by many different GPC matrices.
The GPC matrix representing an (n, k) code is defined by a matrix of 1's and 0's, with M rows and N columns, where N≧n. The columns of the GPC matrix are arranged so that the first n columns correspond to the n bits of the code. The remaining N−n columns correspond to “state variable bits” that help define the code. These state variable bits are sometimes referred to as “hidden bits” or “auxiliary bits.” The value of n must be specified along with the N by M matrix to fully specify a code using the GPC matrix.
Each row of the GPC matrix represents a parity check constraint. The bits involved in the constraint represented by a particular row correspond to the columns that have a 1 in that row. The parity check constraint enforces that the sum of the bits must be even, or equivalently 0 when summed modulo 2. For example, a GPC matrix with N=7
                    [                                            1                                      1                                      1                                      0                                      1                                      0                                      0                                                          0                                      1                                      1                                      1                                      0                                      1                                      0                                                          0                                      0                                      1                                      1                                      1                                      0                                      1                                      ]                            (        1        )            
represents three constraintsx1⊕x2⊕x3⊕x5=0  (2)x2⊕x3⊕x4⊕x6=0  (3)x3⊕x4⊕x5⊕x7=0,  (4)
where the variable xi represents the value of the ith bit, which can be 0 or 1, and the symbol ⊕ represents the modulo 2 sum. This GPC matrix is one way to represent the well-known Hamming (7, 4) code. This code is used an example code transformed below according to the invention.
Some of the M different constraints represented by the GPC matrix may be linearly dependent. In the GPC matrices given in equations (1) and (5), all the constraints are linearly independent. Another representation for the same code is a GPC matrix with N=n=7
                              [                                                    1                                            1                                            1                                            0                                            1                                            0                                            0                                                                    0                                            1                                            1                                            1                                            0                                            1                                            0                                                                    0                                            0                                            1                                            1                                            1                                            0                                            1                                                                    1                                            0                                            0                                            1                                            1                                            1                                            0                                                                    0                                            1                                            0                                            0                                            1                                            1                                            1                                                                    1                                            0                                            1                                            0                                            0                                            1                                            1                                                                    1                                            1                                            0                                            1                                            0                                            0                                            1                                              ]                .                            (        5        )            
In this GPC matrix, the last four rows can be obtained by adding together combinations of the first three rows. This implies that the last four rows are merely redundant constraints, and there are actually only three linearly independent rows. For example, the fourth row can be obtained by adding together the first two rows. For this GPC matrix, there are three linearly independent rows. In general, there will be N−k linearly independent rows in an M by N GPC matrix representation of an (n, k) code.
The GPC matrices given in equations (1) and (5) did not use any hidden bits. Another GPC matrix that uses hidden bits and represents the same code is the GPC matrix, with N=11 and n=7,
                              [                                                    1                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                                                    0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                                                    0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            1                                            0                                                                    0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            1                                            0                                            1                                                                    0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            1                                            0                                                                    0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            1                                                                    0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                              ]                .                            (        6        )            Decoding Methods Based on GPC Matrices
As stated above, prior-art decoding methods that utilize a representation of a code by a GPC matrix include the a posteriori probability propagation (APP) decoding method, belief propagation (BP), and the “sum-product” decoding method. If the same code is represented using two different GPC matrices, then the performance of these decoding methods is also different.
Often, the performance of decoding methods is measured in comparison with an optimal decoder that uses a maximum likelihood (ML) method. The ML decoder scans through all 2k possible code-words, and selects the one that is most likely to have been transmitted. However, the ML decoding method is not practical when k is large.
Generally speaking, the BP decoding method performs somewhat better than the APP decoding method, but at a cost in computational complexity. Other decoding methods based on these methods typically involve a similar trade-off between performance and complexity, but as a class, these decoding methods are considered to be practical for codes with large N and k.
Generally, the iterative decoding methods based on or similar to the BP and APP decoding methods perform reasonably close to ML decoding with GPC matrices that satisfy the following constraints: the number of 1's in each row is small; the number of rows is large; and the number of columns that have a 1 in both rows is small, i.e., ideally zero or one, for any two rows in the matrix.
Many codes, e.g., low-density parity check (LDPC) codes, first described by Gallager, in “Low-density parity check codes,” Vol.21, Research Monograph Series, MIT Press, 1963 or irregular repeat-accumulate (IRA) codes, described by Khandkar et al., in “Irregular Repeat-Accumulate Codes,” 2nd International Symposium on Turbo codes and Related Topics, pp. 1–8, 2000, are designed so that their GPC matrices have these characteristics, insofar as possible. The BP and APP decoding methods work quite well for these codes.
Some codes, e.g., one-step majority logic decodable codes, were designed to use other criteria, but have GPC matrix representations appropriate for BP or APP decoding. The performance of the BP and APP decoding methods is also good for these codes, see Lucas et al., “Iterative Decoding of One-Step Majority Logic Decodable Codes Based on Belief Propagation,” IEEE Transactions on Communications, vol. COM-48, pp. 931–937, 2000.
Other classical codes such as Bose, Chaudhuri, and Hocquenghen (BCH) codes, and codes based on Euclidean or projective geometries also work well with ML decoding and have known GPC matrix representations. However, the known GPC matrix representations for these classical codes do not satisfy the three constraints above, and therefore iterative decoding methods perform poorly.
Therefore, there is a need for a method to transform a GPC matrix representation of a code into another GPC matrix representation of the same code. More particularly, it is desired to transform a GPC matrix representation so that the transformed GPC matrix works better than the original matrix when used with iterative decoding methods.